當模型在生成文字時，每一步都會面臨很多可能的選項，而最終輸出的過程，就叫做解碼（decoding）。

Decoding 的核心問題就是從眾多可能的輸出當中選擇最佳的文字序列。

Beam Search 是序列生成中最常用的演算法之一，它被廣泛應用在翻譯、語音與文本生成任務中。

今天就要來介紹 Beam Search Algorithm～

Beam Search Algorithm 介紹

在解碼（decoding）的階段，常見的方法有：

• Greedy search：每次只看局部機率，選取當下機率最高的單字，雖然快速但可能漏掉更佳的答案（例如 Viterbi Algorithm）
• Beam search：在每個時間步保留前 N 個最佳候選序列（beam width = N），然後再展開，最後挑選最好的完整序列
  → 雖然比 greedy search 需要更多計算，但是會有更好的輸出，也比窮舉法（exhaustive search）來的更有效率
• 因為它cast the light beam（光束） of its search，所以才有這樣的名字
• 因為我們要產出的是一個完整的句子，所以一定要看字和字之間組合的可能性，因此beam search相對於greedy search來說會比較適當

Beam Search 怎麼運作

預設beam width為2

• beam width的大小，會影響演算法的效率以及結果，width大，計算量大，不過得到的結果會比較好，width小，效率高，但是結果不一定是最正確的
• 可以利用grid search來對一個範圍內的width值做測試

以下為運作方式：

1. 在接收編碼器（encoder）的輸出之後，decoder從root開始往右擴展序列
2. 每個位置選出兩個機率最高的字
3. 把這兩個機率最高的字放到下一個位置，跟下一個位置的單字做結合運算，並再繼續看兩個機率最高的組合，直到最後結束
4. 因為在過程中只選出兩個最高機率的組合或單字，因此不需要的節點就去掉，稱作 beam search pruning
5. 這些過程都是需要經由重複計算以確保獲得最好的sequence

Beam search的好處

1. 效率：因為限制了節點數量，因此計算量相對其他演算法來說較少
2. 彈性：針對不同的問題，可以透過調整width或其他參數來彈性應對
3. 可擴展性：可以處理很複雜龐大的問題，因為不用看全部的節點

小結

總結來說，Beam Search Algorithm 在效率與品質之間取得平衡，比 Greedy search 更可靠，也比窮舉法更有可行性，在翻譯、語音辨識與文本生成等需要產出完整序列的任務當中，Beam Search 都是常用的方法之一。